package leetcode;

/*
872. 叶子相似的树
请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。
举个例子，如上图所示，给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。
如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。
如果给定的两个头结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。
示例 1：
输入：root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
输出：true
示例 2：
输入：root1 = [1], root2 = [1]
输出：true
示例 3：
输入：root1 = [1], root2 = [2]
输出：false
示例 4：
输入：root1 = [1,2], root2 = [2,2]
输出：true
示例 5：
输入：root1 = [1,2,3], root2 = [1,3,2]
输出：false
提示：
给定的两棵树可能会有 1 到 200 个结点。
给定的两棵树上的值介于 0 到 200 之间。
*/

import java.util.ArrayList;
import java.util.List;

public class problems_872 {
    public static void main(String[] args) {
        TreeNode A1 = new TreeNode(1);
        TreeNode A2 = new TreeNode(2);
        TreeNode A3 = new TreeNode(3);
        TreeNode A4 = new TreeNode(5);
        A1.left = A2;
//        A1.right = A3;
//        A2.left = A4;

        TreeNode B1 = new TreeNode(1);
        TreeNode B2 = new TreeNode(2);
        TreeNode B3 = new TreeNode(3);
        TreeNode B4 = new TreeNode(4);
        TreeNode B5 = new TreeNode(5);
        B1.right = B2;
//        B1.right = B3;
//        B2.right = B4;
//        B3.right = B5;
        System.out.println(new Solution().leafSimilar(A1, B1));
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    static class Solution {
        public boolean leafSimilar(TreeNode root1, TreeNode root2) {
            List<Integer> list1 = new ArrayList();
            dfs(root1, list1);
            List<Integer> list2 = new ArrayList();
            dfs(root2, list2);
            return list1.equals(list2);
        }
        private void dfs(TreeNode node, List<Integer> list) {
            if(null != node.left) dfs(node.left, list);
            if(null != node.right) dfs(node.right, list);
            if(null == node.left && null == node.right) list.add(node.val);
        }
    }
}